#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const std::vector<T>& vec) {
    for (auto v : vec) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
}

class Solution {
  public:
    int lengthOfLIS(const vector<int>& nums) {
        if (nums.empty()) return 0;
        std::vector<int> stack;  // 记录的是各长度最优末尾大小
        stack.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > stack.back())
                stack.push_back(nums[i]);
            else {
                for (int j = 0; j < stack.size(); ++j) {
                    if (nums[i] <= stack[j]) {
                        stack[j] = nums[i];
                        break;
                    }
                }
            }
            print(stack);
        }
        return stack.size() - 1;
    }
};

int main() {
    // std::vector<int> vec{10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> vec{4, 10, 4, 3, 8, 9};
    Solution s;
    s.lengthOfLIS(vec);
}
